#define _CRT_SECURE_NO_WARNINGS 1


class Solution {
public:
    vector<int> findSubstring(string s, vector<string>& words) {
        unordered_map<string, int> hash2;
        for (string word : words)
        {
            hash2[word]++;
        }

        vector<int> ans;
        int wordsLen = words.size(), wordLen = words[0].size();
        for (int i = 0; i < wordLen; i++)
        {
            unordered_map<string, int> hash1;
            int count = 0;
            int left = i, right = i;
            while (right < s.size())
            {
                string in = s.substr(right, wordLen);
                if (hash2.count(in) && hash1[in] < hash2[in]) count++;
                hash1[in]++;
                if (right - left + 1 == wordLen * wordsLen)
                {
                    if (count == wordsLen) ans.push_back(left);
                    string out = s.substr(left, wordLen);
                    if (hash1[out] <= hash2[out]) count--;
                    hash1[out]--;
                    left += wordLen;
                }
                right += wordLen;
            }
        }
        return ans;
    }
};